package com.review.dfs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FullAlphabet {
    private List<String> findRoad(String str) {
        ArrayList<String> res = new ArrayList<>();
        HashMap<Character, Boolean> map = new HashMap<>();
        for (char c : str.toCharArray()) {
            map.put(c, false);
        }
        dfs(res, map, str, new StringBuilder(), 0);
        return res;
    }

    private void dfs(List<String> res, Map<Character, Boolean> map, String str, StringBuilder sb, int index) {
        if (sb.length() == str.length()) {
            res.add(sb.toString());
            return;
        }
        if (index>=str.length()){
            return;
        }
        for (int i = index; i < str.toCharArray().length; i++) {
            if (!map.get(str.charAt(i))) {
                map.put(str.charAt(i), true);
                dfs(res, map, str, sb.append(str.charAt(i)),index);
                map.put(str.charAt(i), false);
                sb.deleteCharAt(sb.length()-1);
            }
        }
    }

    public static void main(String[] args) {
        FullAlphabet fullAlphabet = new FullAlphabet();
        List<String> abc = fullAlphabet.findRoad("ABC");
        for (String s : abc) {
            System.out.println(s);
        }
    }
}
